package insert;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

//class Solution {
//    public int[][] insert(int[][] intervals, int[] newInterval) {
//        // 合并区间
//        int[][] newIntervals = new int[intervals.length+1][2];
//        int j = 0;
//        boolean bol = true;
//        for (int i = 0; i < newIntervals.length; i++) {
//            if(j<intervals.length&&intervals[j][0] >= newInterval[0]&&bol) {
//                bol = false;
//                newIntervals[i] = newInterval;
//            }else if(j<intervals.length){
//                newIntervals[i] = intervals[j];
//                j++;
//            }else {
//                newIntervals[i] = newInterval;
//            }
//        }
//        return merge(newIntervals);
//    }
//    private int[][]merge(int[][] interval) {
//        LinkedList<int[]> ans = new LinkedList<>();
//        // 合并区间
//        ans.addLast(interval[0]);
//        for (int i = 1; i < interval.length; i++) {
//            if(ans.peekLast()[1] >= interval[i][0]) {
//                ans.peekLast()[1] = Math.max(interval[i][1],ans.peekLast()[1]);
//            }else {
//                ans.add(interval[i]);
//            }
//        }
//        return ans.toArray(new int[ans.size()][]);
//    }
//}
// inter[i][0]<inser[0] inter[i][0] = inter[i]

class Solution {
 //   public int[][] insert(int[][] intervals, int[] newInterval) {
//        int left = newInterval[0];
//        int right = newInterval[1];
//        boolean placed = false;
//        List<int[]> ansList = new ArrayList<int[]>();
//        for (int[] interval : intervals) {
//            if (interval[0] > right) {
//                // 在插入区间的右侧且无交集
//                if (!placed) {
//                    ansList.add(new int[]{left, right});
//                    placed = true;
//                }
//                ansList.add(interval);
//            } else if (interval[1] < left) {
//                // 在插入区间的左侧且无交集
//                ansList.add(interval);
//            } else {
//                // 与插入区间有交集，计算它们的并集
//                left = Math.min(left, interval[0]);
//                right = Math.max(right, interval[1]);
//            }
//        }
//        if (!placed) {
//            ansList.add(new int[]{left, right});
//        }
//        int[][] ans = new int[ansList.size()][2];
//        for (int i = 0; i < ansList.size(); ++i) {
//            ans[i] = ansList.get(i);
//        }
//        return ans;
   // }
}